• 专利附录
  • 专利说明
  • 权利要求
  • 类似技术
  • 同族专利
  • 引用文献
  • 法律状态
  • 优先权
    • 专利摘要:
    An object of the present invention is to provide an efficient message delivery and ordering in multicasting in an overlapping process group environment, and it is an object of the present invention to provide a method and apparatus for efficiently delivering messages and ordering, A method of selecting a process as a central process and configuring a communication path with a two-stage tree structure that is created by linking the central process and all other processes in the group with a group name, and a process for performing multicasting, A method for establishing a single sender side ordering and a multiplexer side ordering by transmitting a message through a message and a process for requiring multiple group ordering in a group receiving the message, Processes Requiring Multiple Group Ordering It relates to a method for forming a multi-group ordering a dedicated process by sending the signal. The use of the communication path generation method and the total ordering method according to the present invention can improve the communication speed and reduce the amount of messages to be processed at the time of communication because the unnecessary communication path does not need to be transmitted when the message is transmitted.
    公开号:KR19990035426A
    申请号:KR1019970057228
    申请日:1997-10-31
    公开日:1999-05-15
    发明作者:권봉경
    申请人:유기범；대우통신 주식회사；
    IPC主号:
    专利说明:

    A total ordering method for multicasting in a nested process group environment (A method of total ordering for multicasting in overlapped process group environments)
    The present invention relates to a global ordering in a nested process group environment in which more than one process may belong to more than one group in common, and more particularly, to a method of generating a communication path capable of delivering a message without going through an unnecessary path And more particularly, to a full-ordering method that uses a communication path to form a single transmitter side ordering, a multiplexer side ordering, and a multiple group ordering.
    Distributed application services such as distributed multimedia systems, video conferencing, and fault tolerant systems have emerged as communication networks have been increasing in speed and bandwidth, and one of the communication functions required for such application services is a process Multicasting, which is a communication method for simultaneously transmitting data to a plurality of processes. A process refers to a communication terminal that can be regarded as a single entity. An arbitrary process may belong to only one process group. However, if a process belongs to more than one process group as shown in FIG. 1 This environment is called a nested process group environment. 1, process b belongs to group G1 and group G2 at the same time, and process c belongs to group G1, group G2 and group G3 at the same time.
    If a sender sends messages m1 and m2 to an arbitrary receiver group, then all the receiver groups send a message to the application process in the same order as a single source ordering, When the messages m1 and m2 are transmitted to one receiving group, all the processes of the receiving group receive multiple source ordering, which delivers the message to the application process in the same order, When messages m1 and m2 are delivered to different receiving groups, they are divided into multiple group ordering, which delivers messages to the application process in the same order in the nested process group.
    An example of a nested process group requiring multiple group ordering is shown in FIG. As shown in FIG. 2, when processes b and c belong to groups G2 and G3 at the same time, and process a sends message m1 to group G2 and process e sends message m2 to group G3, b has m1 Because m2 is received first and m1 is received later, even though m1 is received first and m2 is received later.
    Conventionally, a Molina and Spauster (MS) method is used to generate a message delivery path in a nested process group environment, and this method creates a communication path in a multicasting tree structure including all processes. FIG. 3 shows a tree created using the MS method when the nested process group environment is composed of eight process groups, and each group consists of processes as shown in Table 1 below.
    Process name a b c d e f g h i Group name G1x x G2 x x x G3 x x x x G4 x x xG5 x xG6 x x G7x x G8 x x
    (x marks: the process belonging to each row group)
    As shown in FIG. 3, since the tree structure using the MS method includes all the processes, the same causality can be provided to the processes to be received, which is advantageous in an environment with many overlaps. However, When you want to transmit, you have to go through many unnecessary paths. That is, considering that the process b multicasts to the group g3, in order to transmit to the process e b → c → d → e It is necessary to use the process path of the service.
    SUMMARY OF THE INVENTION Accordingly, the present invention has been made keeping in mind the above problems occurring in the prior art, and an object of the present invention is to provide a communication path setting method of an independent two-tiered structure capable of transmitting a message without unnecessary paths, The purpose is to provide.
    In order to achieve the above object, a total ordering method for multicasting in a nested process group environment according to the present invention is characterized in that, in a method of generating a communication path, a total set including all group names related to communication Gr); As long as there is a group in which there are processes overlapping among the entire set (Gr), the process of all groups is examined to set the most overlapped process as the root of the two-stage tree (if the process with the largest number of overlapped processes If the number of overlaps and the number of group members are both the same, the user selects one of them and sets it as the root.) If the set root and the root Linking all processes other than the root of each group to a group name, and then repeating excluding the group in which the link is generated from the entire set (Gr); If there is no group in which there exists a process overlapping among the entire group Gr and the entire group Gr, an arbitrary process is set as a root for every group remaining in the entire group Gr, And generating an independent two-stage tree by linking all processes other than the multicast group to a group name, wherein the communication path generated by the communication path generation method is used to perform a single- in case the method, the process P i to perform multicasting, the center of the group G k a process relating to the reception, the forming step of performing a direct multi-casting P i; P i is not the center of the process G k, P i is a step of transmitting (Group Information), GI having a central process in the G k the type of message and a (group identifier, a process identifier, a sequence number); And a central process receiving the message and the GI, performing multicasting according to a message reception order, and performing a multi-group sequencing in multicasting using the communication path generated by the communication path generation method A step of selecting a dedicated process as a dedicated process when there is a central process among the processes requiring multiple group ordering; Typical processes for sending a message include sending a message and a GI to a central process of groups to receive the message; Determining whether there is a normal process for each group to receive the message, and then, in the group having the normal process, the dedicated process sends the GI to the central process of the group; The dedicated process performing direct multicasting to a process requiring multiple group ordering; Performing multicasting on normal processes belonging to the group, the central process of each group receiving the message and the GI; And the central process of each group determines if there is a process that requires multiple group ordering to the group to which the message is to be sent, sends a GI and a message to the dedicated process if it is present, And a dedicated process of receiving a message from the central process includes transmitting a message to processes requiring multiple group ordering.
    1 is an overview of a nested process group environment,
    Figure 2 is an overview of a process group requiring multiple group ordering,
    FIG. 3 shows a multicast tree structure using the MS method,
    4 is a flowchart illustrating a method of generating an independent two-stage tree according to the present invention,
    5 is a flow chart of a multicasting method satisfying a single sender side ordering and a multiple side ordering according to the present invention;
    FIG. 6 is a flowchart of a multiple group ordering method according to the present invention;
    FIG. 7 shows a multicast tree structure when using the method according to the present invention,
    FIG. 8 is an overview of a process of performing multiple group ordering according to the present invention.
    9 is a comparative diagram in which the load when MS method and the method according to the present invention are applied while changing the number of processes,
    FIG. 10 is a comparative chart comparing loads when the MS method and the method according to the present invention are applied while varying the size of the group.
    Figure 4 is a group in which the overlapping process in a flowchart illustrating a method of generating the independent two-stage tree used as a communication path according to the present invention, any group name complete set G generation step of r (S401) comprising a, G r presence (S402), a tree generating unit 411 for groups in which overlapped processes exist, and a tree generating step S406 for groups in which there are no overlapping processes, and the independent second stage A detailed description for the creation of the tree follows.
    If it is assumed in step S401 that the total number of groups belonging to the overlapped process group environment is n, Gr is generated as a whole set including all n group names. In step S402, it is checked whether or not there is a group in which there is a process overlapping in the Gr. If such a group exists, the process proceeds to the tree generating unit 411 for groups in which overlapped processes exist, If the existing group is no longer in the Gr, the process proceeds to a tree generation step S406 for groups in which no overlapped process exists.
    In step S403, the processes in all the groups are examined to set the process that is most overlapped as the root of the two-stage tree. If there are more than two processes with the largest number of overlaps, set those with more group members as the root, and if the number of overlaps and the number of group members are the same, arbitrarily selected from among these groups and set as root. In step S404, a link is created as a group identifier below the route set in step S403, and the corresponding processes are located.
    In step S405, the group in which the link is generated is excluded from the Gr, and then the process returns to step S402 to determine the current Gr.
    In step S406, it is determined whether or not a group remains in Gr. If such a group remains, there is no overlapping process among the remaining groups. Therefore, an arbitrary route is set for each group, Create a tree.
    FIG. 5 is a flowchart of a multicasting method that satisfies a single sender side ordering and a multiple sender side ordering according to the present invention. When a route set by the procedure of FIG. 4 is defined as a central process, The detailed method of ordering is as follows.
    Determine the application center of the process to transmit a message m at step S501 P i is a group G k relating to the reception of the m process, and the determination result is P i is the flow advances to step S504, if the center of the G k process P i is directly Perform multicasting. However, if it is determined in step S501 that P i is not the central process of G k, the process proceeds to step S 502 where P i transmits m and GI to the central process of G k , and then m and G i are transmitted. Multicasting is performed according to the message reception order (step S503).
    FIG. 6 is a flowchart of a multiple group ordering method according to the present invention. When a dedicated process is defined as one process dedicated to multiple group ordering among processes requiring multiple group ordering, Will be described in detail with reference to FIG.
    First, in step S601, a dedicated process to be dedicated to multiple group ordering is selected among the processes requiring multiple group ordering. If there is a central process among the processes requiring multiple group ordering, the dedicated process is selected as a dedicated process. The process with a small number of overlaps is selected as a dedicated process.
    In step S602, the normal processes to send a message send a message and GI (Group Information) to the central process of the group. In step S603, it is determined whether there is a normal process for each group related to reception. In step S604, the process proceeds to step S605. In the group having the normal process, the process proceeds to step S604, The GI is sent to the central process of the group, and the process proceeds to step S605. In step S605, the dedicated process proceeds to step S606 where multicasting is performed directly to a process requiring multiple group ordering.
    In step S606, the central process of each group receiving the message and the GI performs multicasting to the normal processes belonging to the group in step S602. Then, the central process of each group determines whether there is a process requiring multiple group ordering in step S607. If there is a process, the process proceeds to step S608 to transmit a GI and a message to the dedicated process, and then proceeds to step S609, The dedicated process that receives the message sends a message to processes that require multiple group ordering.
    An embodiment for generating a tree structure for an overlapping process group environment having the structure shown in Table 1 according to the method proposed by the present invention will be described in detail with reference to FIG. 4 and FIG.
    G1, G2, G3, G4, G5, G6, G7, G8} at this time. In step S402, it is determined whether or not there is a group in which a process overlapped in the Gr exists. Since such a group exists, the process proceeds to step S403. In step S403, the root of the tree has to be set. Since the process d is superposed four times in total for all the groups from the group G1 to the group G8 remaining in the Gr, the process is superimposed with the greatest number of times in each process, Accordingly, process d 701 is set as the root process. In step S404, a link 702 is created as a group identifier under the process d 701 set as the root, and the processes 703, 704, 705, and 706 are located. In step S405, G1, G3, G4, and G8, in which the link 702 has already been created, are excluded from Gr.
    In step S402, it is determined whether or not there is a group remaining in the Gr, even though there is a process overlapping in the Gr. As a result, the groups G2, G5, G6, And G6 overlap each other in the process b. Therefore, the process goes back to step S403. In order to set the route in step S403, if the number of times that each process is included is compared, it is determined that the process b or the process c is overlapped twice twice and the number of processes is the largest among the groups to which the two processes belong The group is G, which is the same for processes b and c, so arbitrarily set process b to root 711. Next, in step S404, a link 712 is created as a group identifier under the route b 711, and then the processes 713 and 714 are located. In step S405, G2 and G6 are excluded from the Gr.
    Then, the process proceeds to step S402 where it is determined whether or not there is a group remaining in the Gr without generating a link. As a result, the groups G5 and G7 in which links have not yet been generated remain, while the group G5 is composed of processes e and f, Processes c and h do not exist, so there is no overlapping process. Therefore, the flow advances to step S406 to set arbitrary routes 721 and 731 for each group remaining in the Gr, create the links 722 and 732, and then locate the processes 723 and 733. As a result, the tree structure is completed as shown in FIG. 7, and the processes d, b, e, and c set as the root become the central processes.
    That is, if the process b performs multicasting to the group G3, b sends a message to the central process 701, and d 701 sends a message to c and e, so multicasting is possible without going through unnecessary paths, The service time is shortened.
    According to the method proposed by the present invention, in a situation where process a sends message m1 to group G2 and process e sends message m2 to group G3 in the overlapping process group environment of the structure shown in Table 1, P1 803 is added to the group G3 and the process P2 804 is added to the group G3.
    First, in step S601, a dedicated process to be dedicated to multiple group ordering among b (801) and c (processes requiring multiple group ordering) is selected. Since process b 801 is a central process as shown in Fig. 7, 801) as a dedicated process.
    Normal process which are processes a and e to send the message in step S602 transmits to the process b (801) and d (802) driven processes in the group, each message m1 and GI 1, 2 m2 and GI.
    Then, in step S603, it is determined whether or not there is a normal process for each group related to reception. Since the normal process P1 (803) exists in the group G2 and the process P2 (804) exists in the group G3, the process proceeds to step S604 do. In step S604, the dedicated process b 801 sends GI 3 and GI 4 to the central process b 801 of G2 and the central process d 802 of G3, respectively, and proceeds to step S605. In step S605, the dedicated process b 801 directly multicasts the process c that requires multiple group ordering, and transmits the message m1. In step S606, the central process b 801 usually sends to process P1 803 and the central process d 802 usually multicasts to process P2 804 to transmit messages m1 and m2, respectively.
    Since the process that requires a multi-group ordering present in the group to send the message in step S607, the center process d (802) is transmitted to a dedicated process b (801) the GI 5 with messages m2 at step S608, and step S609 The dedicated process b 801 that has received the message m2 from the central process 802 transmits the m2 received in step S608 to the processes requiring the multiple group ordering in the order in which they are received.
    That is, as shown in FIG. 8, it can be seen that m1 arrives first in process b (801), m2 arrives later, and message arrives in process c in the same order.
    Below, we compare the number of messages and delay time required for multicasting using the method according to the present invention and the conventional MS method for a point-to-point network and a broadcasting network .
    In a point-to-point network, when a sender performs multicasting to n processes, n messages are needed because they need to be transmitted to each recipient.
    The number of messages required for multiple group ordering for multicasting is N, the time from the start of multicasting to the receipt of a message by all processes in a nested process group environment is T, and the sender transmits to the network for multicasting P is the internal processing time, and L is the delay time until the message arrives at the target process through the network. Assuming that P and L are constants, ε Is the number of processes that need to go through unnecessarily, then the number of messages required by the MS method is n + to be. Even when using the MS method ε Is N = n, then according to the method according to the present invention, N = n is always used since it does not go through an unnecessary process at all times.
    Also, in order to compare the total delay time according to multicasting, when the MS method is used, if the longest path among the processes from the process located at the top of the tree to each member of the target group among processes of the target group is d, The maximum delay time is the sum of the delay from the sender to the process at the highest position in the destination group and the delay from the highest process to the longest path. Here, the delay from the sender to the highest- L + P , And the delay from the top-level process to the process with the longest path d in the destination group dxL + (n-1 + ) xP to be. That is, the maximum delay is (d + 1) L + (n + ) P to be. The minimum delay is when the top-level process performs multicasting, since there is no delay time L until the message reaches the destination process through the network d x L + (n + epsilon) x P to be.
    The number of processes requiring total ordering to obtain the delay using the method of the present invention is x. Then the maximum delay is usually the delay from the process to the central process L + P , Delays from the central process to the dedicated process and the rest of the target group L + (nx) xP , Delays from dedicated processes to processes that require full sequencing L + (x-1) xP . Therefore, the total delay 3 x L + n x P to be. The minimum delay occurs when the central process is the sender and no processes need full ordering, in which case the total delay L + n x P to be. That is, when using the method of the present invention, the total delay time is d ε .
    When the overall ordering method and the total ordering method according to the present invention are applied to the point-to-point network by the conventional MS method, the number of messages required for multicasting and the total delay time results are shown in the following table 2.
    MS methodThe method of the present invention Number of messages (N) n N n + N = n Total delay time (T) dxL + (n + ) x P T (d + 1) L + (n + ) PL + n x P T 3 x L + n x P
    Also, in a broadcast network, when a sender transmits a message, all the receivers connected to the network receive the message at a time. When applying the MS method, the maximum number of messages is the sum of the number of messages transmitted from the sender to the highest process of the multicasting tree among the members of the group and the number of messages transmitted to the destination process from the highest process to be. That is, the maximum number of messages required for multicasting is d + 1. The minimum number of messages is d.
    When the method according to the present invention is used, the maximum number of messages is the number of messages required for transfer from a normal process to a central process, from a central process to a dedicated process, from a dedicated process to a process requiring a total ordering And the minimum number of messages is the number of messages required when the central process performs multicasting to members of the group.
    Let C be the time for confirming whether the message is a destination due to the characteristics of the broadcasting network. In case of using the MS method, the maximum delay is the delay from the transmitting side to the highest process P + L + C And the delay through the longest path d x (P + L + C) . The minimum delay is the delay value transmitted directly from the top-level process d x (P + L + C) to be. When using the method of the present invention, the minimum delay is P + L + C , And the maximum delay is 3 x (P + L + C) to be.
    Table 3 below shows the results of applying the total ordering method according to the conventional MS method and the total ordering method according to the present invention to a broadcasting network.
    MS methodThe method of the present invention Number of messages (N) d N d + 11 N 3 Total delay time (T) d x (P + L + C) N (d + 1) x (P + L + C)(P + L + C) N 3 x (P + L + C)
    FIGS. 9 and 10 show the number of generated trees (the number of central processes) and the number of messages to be processed for completion of multicasting, while changing each element for the number of fixed total processes, Is a result of measuring the load of a multicast group. When it is assumed that all the members of a group multicast a message once, a value obtained by comparing how many messages each multicast message should be processed to arrive at all groups . Here, the load is the number of messages included in the transmission and reception in the multicasting communication.
    In order to achieve the total ordering in the overlapping process group environment by the conventional MS method, all the processes in the environment are included in the tree structure representing the message transmission path. Therefore, when a message is transmitted from one process to another process, However, if the total ordering method according to the present invention is used, such an unnecessary path is eliminated and the communication speed is improved and the amount of messages is reduced. Also, as shown in FIG. 9, as the number of processes increases, and as shown in FIG. 10, the smaller the group size, the MS method, or the method according to the present invention, or the load becomes similar to each other . Therefore, the method of the present invention can be more efficiently used when the size of a group is determined, the total number of processes is reduced, and the total number of processes is determined.
    权利要求:
    Claims (3)
    [1" claim-type="Currently amended] Generating a whole set (Gr) including all group names related to communication;
    As long as there is a group in which there is a process overlapping among the entire set (Gr), the process of all the groups is examined to set the most overlapped process as the root of the two-stage tree If the number of overlaps and the number of group members are both the same, the user selects one of them and sets it as the root.) If the set root and the root Linking all processes other than the root of each group to a group name, and then repeating excluding the group in which the link is generated from the entire set (Gr); And
    If there is no group in which there is a process overlapping among the entire set Gr, an arbitrary process is set as a root for all the groups remaining in the entire set Gr, And linking all processes to a group name to generate an independent two-tier tree.
    [2" claim-type="Currently amended] A method for performing multicasting using a communication path generated by the method of claim 1,
    If the process P i to perform multicasting is a central process of a group G k related to reception, P i directly performs multicasting;
    P i is not the center of the process G k, P i is a step of transmitting (Group Information), GI having a central process in the G k the type of message and a (group identifier, a process identifier, a sequence number); And
    Wherein the central process having received the message and the GI includes performing multicasting according to a message reception order, thereby forming a single transmitter side ordering and a multiple destination side ordering.
    [3" claim-type="Currently amended] A method for performing multicasting using a communication path generated by the method of claim 1,
    Selecting a dedicated process as a dedicated process when there is a central process among the processes requiring multiple group ordering;
    Typical processes for sending a message include sending a message and a GI to a central process of groups to receive the message;
    Determining whether there is a normal process for each group to receive the message, and then, in a group having a normal process, the dedicated process sends a GI to the central process of the group;
    The dedicated process performing direct multicasting to a process requiring multiple group ordering;
    Performing multicasting on normal processes belonging to the group, the central process of each group receiving the message and the GI; And
    The central process of each group determines whether there is a process that requires multiple group ordering to the group to which the message is to be sent, if it exists, it sends a GI and a message to the dedicated process, usually sends a direct message to the process, Wherein the dedicated process receiving the message from the process comprises sending a message to processes requiring multiple group ordering.
    类似技术:
    公开号 | 公开日 | 专利标题
    TWI291293B|2007-12-11|Method and apparatus for performing coverage control for multicast services in a wireless network
    DE19505905B4|2007-02-22|Method and apparatus for adaptive routing in a communication system
    EP0403529B1|1995-05-17|Mixed mode compression for data transmission
    DE69532262T2|2004-09-30|Multiple transmission method
    CN101057457B|2012-09-05|Device for serving the transmission area and its operation method
    JP4044901B2|2008-02-06|Method for transmitting data from one transmitter to a plurality of receivers
    US7333488B2|2008-02-19|Multicast delivery control apparatus and method
    US6611528B1|2003-08-26|Hierarchical routing knowledge for multicast packet routing
    JP3306163B2|2002-07-24|Method of conducting a signal through a switch and a switching node
    EP1155535B1|2006-06-14|Methods for implementing a talkgroup call with competing sources in a multicast ip network
    US7158514B2|2007-01-02|Multicast routing method and apparatus for routing multicast packet
    US6321270B1|2001-11-20|Method and apparatus for multicast routing in a network
    KR100412296B1|2003-12-31|Method and apparatus for routing packet data in a communications system
    EP2285145B1|2012-05-23|Methods for implementing a talkgroup call in a multicast IP network
    EP1344360B1|2009-11-11|Wireless communication system incorporating multicast addressing and method for use
    CN101960801B|2014-05-21|Technique for determining a point-to-multipoint tree linking a root node to a plurality of leaf nodes
    JP4328283B2|2009-09-09|Packet delivery control method
    US7787449B2|2010-08-31|Butterfly network with switches set for two node disjoint paths and method for forming the paths
    EP0570547B1|1999-02-03|Technique for measuring channel delay
    US7751394B2|2010-07-06|Multicast packet relay device adapted for virtual router
    EP0780046B1|2005-03-16|Atm communication with inverse multiplexing over multiple links
    US7254132B2|2007-08-07|Mobile communication system, mobile communication method, wireless base station, mobile station, and program
    AU2002312463B2|2005-09-15|A method for improving packet delivery in an unreliable environment
    AU2006223440C1|2010-02-18|Multi-node communication system and method of requesting, reporting and collecting destination-node-based measurements and route-based measurements
    JP3605121B2|2004-12-22|Distributed control switching network for multi-line telephony.
    同族专利:
    公开号 | 公开日
    KR100252506B1|2000-04-15|
    引用文献:
    公开号 | 申请日 | 公开日 | 申请人 | 专利标题
    法律状态:
    1997-10-31|Application filed by 유기범, 대우통신 주식회사
    1997-10-31|Priority to KR1019970057228A
    1999-05-15|Publication of KR19990035426A
    2000-04-15|Application granted
    2000-04-15|Publication of KR100252506B1
    优先权:
    申请号 | 申请日 | 专利标题
    KR1019970057228A|KR100252506B1|1997-10-31|1997-10-31|A method of total ordering for multicasting in overlapped process group environments|
    [返回顶部]